This invention relates to digital communication; more particularly it relates to a method and apparatus for the detection and correction of errors in digital data occurring during communication of the data. Communication is used in the broad sense to include transmission over conductors, telephone lines and the like, radio and television broadcasting and digital data signal recording and playback.
There has been a demand for increased quality of audio recording and read back systems as well as in other types of communications. One type of audio recording and read back system takes analog audio signals, converts the signals to digital form, records the digital form of signals on a recording media, reads back the digital form of signals, converts the digital form of the signals to analog form, and then applies the analog form of the signals to an audio speaker. Modern systems record the digital data on a variety of recording media. One high quality recording media is an optical disk.
One problem with recording media is that there are defects in the media and as a result there are areas where the digital data is not recorded properly or cannot be reliably read back and as a result errors occur in the digital read back data. Errors also occur in transmissions of digital data. During recording, read back and transmission of digital data, errors occur in the digital data with some finite probability. The data is typically composed of binary units, a group of binary bits (such as 8) make up a data "byte", and groups of bytes (such as 2) make up a data "word". Additionally the data is arranged into "blocks" of data (such as 32 or 28 byte blocks). The errors which occur are considered to be of two types, although there is undoubtedly some overlap between the two. The first such type is a single bit error, which is the substitution of one of two possible values of a binary bit for its opposite value. Such errors usually occur randomly in a digital signal. A second type of error consists of a continuous sequence of erroneous bits. Such errors are referred to as "burst errors." The length of these bursts and their frequency of occurrence are also random.
An approach to the inevitable occurrence of errors in a digital signal is to include additional or redundant bits in the signal which will allow for detection and correction of such errors. The process whereby such redundant bits are added to information is called encoding; the information bits plus redundant bits form the code. The costs of such a strategy are increased time for processing the data after transmission, the extra equipment needed and the decrease in the amount of information which can be transmitted per unit time because of the extra bits included for error detection and correction. As the number of errors which can be corrected by any code increases, the number of bits which must be added to the data to enable such correction also increases. Accordingly, there has been considerable effort directed to finding efficient codes. Efficiency in this context is measured by the ratio of information or data bytes to data bytes plus data correction or "parity" bytes; it is also measured by the number of errors which can be corrected (typically expressed as the number of errors remaining after correction for an assumed initial error frequency). From a theoretical viewpoint, it has been found that the Reed-Solomon class of block codes are among the most efficient coding schemes yet devised. The efficiency of any code, in practical use, also depends on the implementing equipment.
In recent years there has been great interest in utilizing Reed-Solomon codes for recording, read back and transmission of audio information, especially in the recording industry, where high fidelity is at a premium. For example, Vries et al. describes a digital audio disk system in a paper entitled The Compact Disc Digital Audio System (Abstract 1674 [H-8]), presented at the 67th Convention of the Audio Engineering Society) wherein audio data was encoded in a crossinterleaved Reed-Solomon code (CIRC) and stored on a small optical disk. An improved method employing the same coding scheme referred to as the Super Strategy, was presented in 1982 by Odaka, et al. at the 71st Convention of the Audio Engineering Society in a paper entitled LSI For Digital Signal Processing To Be Used in Compact Disc Digital Audio Players (Abstract 1860 [G-5]).
In implementing the CIRC, Odaka discloses that digitized data is, as a first step, expressed in of elements of a finite field. Such representations are termed Galois numbers. The relationship between the original data and its corresponding Galois representation is specified by a primitive polynomial, which is chosen from among a plurality of known primitive polynomials and is described by way of example by Peterson and Weldon in a book entitled Error Correcting Codes, published in 1972 by the MIT Press. Each data element is a representation of a coefficient of a power of an irreducible root of the chosen primitive polynomial. This root is commonly indicated as .alpha.. The CIRC then utilizes a two-step encoding process. In passing through the first encoder, 24 consecutive data bytes which are representations of a data polynomial are divided by a generator polynomial. The generator polynomial is also a function of the root .alpha.. In the process, four parity bytes are added. The result is a block of 24 data bytes and 4 parity bytes. This consecutive sequence of bytes is interleaved or dispersed among other encoded data bytes. The interleaved data is passed through the second encoder. The second encoder is identical to the first except that the bytes are presented in a different sequence because of interleaving, parity bytes together with data bytes are being encoded, blocks of 28 bytes (24 data bytes plus 4 parity bytes) are being encoded instead of 24 byte blocks, and 4 additional parity bytes are added. The result of the second encoding process is a 32 byte block composed of 24 data bytes and 8 parity bytes.
The encoded data is optically recorded and subsequently read back. After the encoded data is read back, there will be data errors due to recording, read back or transmission problems. The parity symbols in the data are then used to detect and correct any errors which may have occurred. Such errors may occur in the information or in the parity symbols. In the system reported in the Odaka papers (supra), two separate decoders, C1 and C2, are used to decode the previously encoded data. Thirty-two consecutive data bytes (a C1 block) are divided by a generator polynomial in the C1 decoder. Using the remainders resulting from this division the C1 decoder is able to correct up to two errors in the 28 high order bytes. Significantly, the 4 low order parity bytes are discarded and the remaining bytes are de-interleaved using delay lines implemented by shift registers. Only the 28 remaining bytes (a C2 block) are then decoded by a C2 decoder. Both the C1 and C2 decoders set erasure flags for each byte in blocks where an error pattern cannot be corrected or where it is determined that there is reason to doubt that a particular correction is in fact correct. The erasure flags are utilized in subsequent steps to conceal these errors by interpolation or by repeating the data bytes in the immediately preceding data block to cover the block in error.
The Odaka method does not fully utilize the error detection and correction capabilities of the CIRC code. For example, errors may occur in the 4 lowest order parity bytes of a C1 block. Since these are only treated as parity bytes by the C1 decoder (i.e., they are never corrected by it) and are discarded before reaching the C2 decoder, such errors are never correctable. Such incorrect parity bytes will result in miscorrection (erroneous changes) of data bytes by the C1 decoder and ultimately degrade the performance of the code.